{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Non-overlapping Intervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: eraseOverlapIntervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无重叠区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个区间的集合&nbsp;<code>intervals</code>&nbsp;，其中 <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>&nbsp;。返回 <em>需要移除区间的最小数量，使剩余区间互不重叠&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> intervals = [[1,2],[2,3],[3,4],[1,3]]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 移除 [1,3] 后，剩下的区间没有重叠。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> intervals = [ [1,2], [1,2], [1,2] ]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 你需要移除两个 [1,2] 来使剩下的区间没有重叠。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> intervals = [ [1,2], [2,3] ]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 你不需要移除任何区间，因为它们已经是无重叠的了。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= intervals.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>intervals[i].length == 2</code></li>\n",
    "\t<li><code>-5 * 10<sup>4</sup>&nbsp;&lt;= start<sub>i</sub>&nbsp;&lt; end<sub>i</sub>&nbsp;&lt;= 5 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [non-overlapping-intervals](https://leetcode.cn/problems/non-overlapping-intervals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [non-overlapping-intervals](https://leetcode.cn/problems/non-overlapping-intervals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[3,4],[1,3]]', '[[1,2],[1,2],[1,2]]', '[[1,2],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self,intervals):\n",
    "        end = float('-inf')\n",
    "        res = 0\n",
    "        \n",
    "        intervals = sorted(intervals,key=lambda e:e[-1])\n",
    "        \n",
    "        for event in intervals:\n",
    "            if event[0] < end:\n",
    "                res += 1\n",
    "            else:\n",
    "                end = event[-1]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        intervals.sort(key=lambda x:x.end)\n",
    "        \n",
    "        res=0\n",
    "        tmp=float('-inf')\n",
    "        \n",
    "        for x in intervals:\n",
    "            if x.start<tmp:\n",
    "                res+=1\n",
    "            else:\n",
    "                tmp=x.end\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "from functools import cmp_to_key\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(intervals) <= 0:\n",
    "            return 0\n",
    "        intervals = sorted(intervals, key=lambda x: x.end)\n",
    "        cnt = 1\n",
    "        end = intervals[0].end\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i].start < end:\n",
    "                continue\n",
    "            end = intervals[i].end\n",
    "            cnt += 1\n",
    "        return len(intervals) - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for an interval.\n",
    "# class Interval:\n",
    "#     def __init__(self, s=0, e=0):\n",
    "#         self.start = s\n",
    "#         self.end = e\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[Interval]) -> int:\n",
    "        if not len(intervals):\n",
    "        \treturn 0\n",
    "        intervals = sorted(intervals, key=lambda k:k.end)\n",
    "        minEnd = intervals[0].end\n",
    "        rest = 1\n",
    "        for i in range(1,len(intervals)):\n",
    "        \tif intervals[i].start < minEnd:\n",
    "        \t\tcontinue\n",
    "        \trest += 1\n",
    "        \tminEnd = intervals[i].end\n",
    "\n",
    "        return len(intervals) - rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        count  =1\n",
    "        intervals.sort(key=lambda x: x[1])\n",
    "        if len(intervals)<=1:\n",
    "            return 0\n",
    "        tmp =intervals[0][1]\n",
    "        for i in range(1,len(intervals)):\n",
    "            if  tmp<=  intervals[i][0]:\n",
    "                tmp = intervals[i][1]\n",
    "                count +=1\n",
    "        return len(intervals)-count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        intervals = sorted(intervals,key=lambda x:x[0]) \n",
    "        num = len(intervals)    \n",
    "        effect = [intervals[0]]\n",
    "        for interval in intervals[1:]:\n",
    "            if interval[0]>=effect[-1][1]:\n",
    "                effect.append(interval)\n",
    "            else:\n",
    "                if interval[1] >= effect[-1][1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    effect.pop()\n",
    "                    effect.append(interval)\n",
    "        \n",
    "        return num - len(effect)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: \n",
    "        res = 1\n",
    "        if not intervals: return 0\n",
    "        def cmp( a, b ):\n",
    "            if (a[1]-b[1]) < 0:\n",
    "                return -1\n",
    "            if (a[1]-b[1]) == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        import functools\n",
    "        # it2 = sorted(intervals,key = functools.cmp_to_key(cmp))\n",
    "        it2 = sorted(intervals,key = lambda x:x[1])\n",
    "        print(it2)\n",
    "        end = it2[0][1]\n",
    "        for i in range(1,len(it2)):\n",
    "            if it2[i][0] < end :\n",
    "                continue\n",
    "            end = it2[i][1]\n",
    "            res += 1\n",
    "\n",
    "        print(len(intervals) , res)\n",
    "        return  len(intervals) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        intervals.sort(key=lambda x:(x[1]))\n",
    "        end = intervals[0][1]\n",
    "        n = len(intervals)\n",
    "        count = 1\n",
    "        for left, right in intervals[1:]:\n",
    "            if left >= end:\n",
    "                end = right\n",
    "                count += 1\n",
    "        return n - count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals) < 2:\n",
    "            return 0\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        res = 0\n",
    "        p = 1\n",
    "        while p < len(intervals):\n",
    "            if intervals[p][0] < intervals[p-1][1]:\n",
    "                intervals.pop(p) if intervals[p][1] >= intervals[p-1][1] else intervals.pop(p-1)\n",
    "                res += 1\n",
    "            else:\n",
    "                p += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], x[1]))\n",
    "        iLen = len(intervals)\n",
    "        iRemove = 0\n",
    "        iCmp = 0\n",
    "        for i in range(iLen - 1):\n",
    "            a, b = intervals[iCmp]\n",
    "            x, y = intervals[iCmp + 1]\n",
    "            if x >= b:\n",
    "                iCmp += 1\n",
    "                continue\n",
    "            elif y > b:\n",
    "                iRemove += 1\n",
    "                intervals.pop(iCmp + 1)\n",
    "            elif y <= b:\n",
    "                iRemove += 1\n",
    "                intervals.pop(iCmp)\n",
    "        return iRemove\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        length = len(intervals)\n",
    "        if length <= 1:\n",
    "            return 0\n",
    "        res = 0\n",
    "\n",
    "        partArr = sorted(intervals, key=lambda ele: (ele[1], -ele[0]))\n",
    "\n",
    "        nowPar = partArr[0]\n",
    "        for i in range(1, length):\n",
    "            if partArr[i][0] < nowPar[1]:\n",
    "                res += 1\n",
    "                # 跳过了一个，计数1，相当于删了一个\n",
    "                continue\n",
    "            else:\n",
    "                nowPar[1] = partArr[i][1]  # 右端拓展\n",
    "            ...\n",
    "        ...\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        lens={}\n",
    "        starts=[]\n",
    "        ends=[]\n",
    "        s=0\n",
    "        alls=0\n",
    "        for i in intervals:\n",
    "            tp=tuple(i)\n",
    "            lens[tp]=i[1]\n",
    "            starts.append(i[0])\n",
    "            ends.append(i[1])\n",
    "            alls+=1\n",
    "        \n",
    "        l=sorted(lens.items(),key=lambda x:x[1])\n",
    "        min_val=min(starts)\n",
    "        s=max(ends)-min_val+1\n",
    "        zeros=[0]*s\n",
    "        c=0\n",
    "        for i in l:\n",
    "            x=i[0][0]\n",
    "            y=i[0][1]\n",
    "            lst=zeros[x-min_val:y-min_val]\n",
    "            if 1 not in lst:\n",
    "                c+=1\n",
    "                for j in range(x,y):\n",
    "                    \n",
    "                    t=j-min_val\n",
    "                    zeros[t]=1\n",
    "        print(alls)\n",
    "        print(c)\n",
    "        return alls-c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals)==0:\n",
    "            return 0\n",
    "        m = set()\n",
    "        for i in intervals:\n",
    "            for j in i:\n",
    "                m.add(j)\n",
    "        m = list(m)\n",
    "        m.sort()\n",
    "        rev_m = dict(zip(m, [x for x in range(len(m))]))\n",
    "        m = dict(zip([x for x in range(len(m))], m))\n",
    "        interval_dict = {}\n",
    "        for i in intervals:\n",
    "            if i[1] not in interval_dict:\n",
    "                interval_dict[i[1]] = []\n",
    "            interval_dict[i[1]].append(i[0])\n",
    "        dp = [0]*(len(m))\n",
    "        for i in range(len(dp)):\n",
    "            if i in m and m[i] in interval_dict:\n",
    "                for j in interval_dict[m[i]]:\n",
    "                    dp[i] = max(dp[i], dp[rev_m[j]]+1)\n",
    "            dp[i] = max(dp[i], dp[i-1])\n",
    "        return len(intervals)-dp[len(dp)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import unittest\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # noinspection PyMethodMayBeStatic\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        row = len(intervals)\n",
    "        if row <= 1:\n",
    "            return 0\n",
    "        col = len(intervals[0])\n",
    "        # 按end升序, start降序排序\n",
    "        intervals.sort(key=lambda x: (x[1], -x[0]))\n",
    "        count = 0\n",
    "        end = intervals[0][1]\n",
    "        for i in range(1, row):\n",
    "            if intervals[i][0] >= end:\n",
    "                end = intervals[i][1]\n",
    "            else:\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "# class ExampleTest(unittest.TestCase):\n",
    "\n",
    "#     def test0(self):\n",
    "#         pass\n",
    "\n",
    "#     def test1(self):\n",
    "#         sl = Solution()\n",
    "#         intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]\n",
    "#         ans = sl.eraseOverlapIntervals(intervals)\n",
    "#         self.assertEqual(ans, 1)\n",
    "\n",
    "#     def test2(self):\n",
    "#         sl = Solution()\n",
    "#         intervals = [[1, 2], [1, 2], [1, 2]]\n",
    "#         ans = sl.eraseOverlapIntervals(intervals)\n",
    "#         self.assertEqual(ans, 2)\n",
    "\n",
    "#     def test3(self):\n",
    "#         sl = Solution()\n",
    "#         intervals = [[1, 2], [2, 3]]\n",
    "#         ans = sl.eraseOverlapIntervals(intervals)\n",
    "#         self.assertEqual(ans, 0)\n",
    "\n",
    "#     def test4(self):\n",
    "#         pass\n",
    "\n",
    "#     def test5(self):\n",
    "#         pass\n",
    "\n",
    "#     def test6(self):\n",
    "#         pass\n",
    "\n",
    "#     def test7(self):\n",
    "#         pass\n",
    "\n",
    "#     def test8(self):\n",
    "#         pass\n",
    "\n",
    "#     def test9(self):\n",
    "#         pass\n",
    "\n",
    "#     def test10(self):\n",
    "#         pass\n",
    "\n",
    "\n",
    "# if __name__ == '__main__':\n",
    "#     unittest.main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals)<=1:\n",
    "            return 0\n",
    "        self.quicksort(intervals,0,len(intervals)-1) #根据第一个值进行升序排序\n",
    "        end = intervals[0][1] #记录当前最小结束时间点\n",
    "        cnt = 0\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0]<end:\n",
    "                #有重叠\n",
    "                cnt+=1\n",
    "                end = min(end,intervals[i][1])\n",
    "            else:\n",
    "                end = intervals[i][1]\n",
    "        return cnt\n",
    "    def quicksort(self,nums,l,r):\n",
    "        if l>=r:\n",
    "            return \n",
    "        i = l\n",
    "        j = r\n",
    "        key = nums[l]\n",
    "        while i<j:\n",
    "            while i<j and nums[j][0]>=key[0]:\n",
    "                j-=1\n",
    "            nums[i] = nums[j]\n",
    "            while i<j and nums[i][0]<key[0]:\n",
    "                i+=1\n",
    "            nums[j] = nums[i]\n",
    "        nums[i] = key\n",
    "        self.quicksort(nums,i+1,r)\n",
    "        self.quicksort(nums,l,i-1)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self,intervals):\n",
    "        k1 = len(intervals)\n",
    "        intervals.sort(key=lambda x:(x[1]))\n",
    "        i = 0\n",
    "        while(i<len(intervals)-1):\n",
    "            if intervals[i][1]>intervals[i+1][0]:\n",
    "                del intervals[i+1]\n",
    "                self.eraseOverlapIntervals(intervals)\n",
    "            i += 1\n",
    "        k2 = len(intervals)\n",
    "        return k1-k2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "\n",
    "        def dfs(end, i):\n",
    "            if i == len(intervals): return 0\n",
    "\n",
    "            if intervals[i][0] < end:\n",
    "                return 1 + dfs(min(end, intervals[i][1]), i + 1)\n",
    "            else:\n",
    "                return dfs(intervals[i][1], i + 1)\n",
    "\n",
    "        return dfs(float('-inf'), 0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        intervals = sorted(intervals,key=lambda x:x[0])\n",
    "        size = len(intervals)\n",
    "\n",
    "        cache = {\n",
    "            size - 1 : 1,\n",
    "        }\n",
    "        def impl(i):\n",
    "            if i in cache:\n",
    "                return cache[i]\n",
    "\n",
    "            result = impl(i + 1)\n",
    "            for j in range(i+1,size):\n",
    "                if intervals[i][1] <= intervals[j][0]:\n",
    "                    result = max(result,1+impl(j))\n",
    "                    break\n",
    "            result = max(result,1)\n",
    "            cache[i] = result\n",
    "            return result \n",
    "\n",
    "\n",
    "        return size - impl(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "\n",
    "        intervals.sort()\n",
    "        result = 0\n",
    "\n",
    "        for i in reversed(range(len(intervals)-1)):\n",
    "            if (intervals[i][1]>intervals[i+1][0]):\n",
    "                result += 1\n",
    "                intervals.pop(i)\n",
    "        \n",
    "        return result\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        ans=0\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0]<intervals[i-1][1]:\n",
    "                ans+=1\n",
    "                intervals[i]=intervals[i-1]\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        ans=0\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0]<intervals[i-1][1]:\n",
    "                ans+=1\n",
    "                intervals[i]=intervals[i-1]\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] < intervals[i-1][1]:\n",
    "                ans += 1\n",
    "                if intervals[i][1] > intervals[i-1][1]:\n",
    "                    intervals[i] = intervals[i-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        # end_map = {}\n",
    "        ans = 0\n",
    "        # for start, end in intervals:\n",
    "        #     if start in end_map:\n",
    "        #         ans += 1\n",
    "        #     end_map[start] = min(end_map.get(start, 10 ** 6), end)\n",
    "\n",
    "        # intervals = [[k, v] for k, v in end_map.items()]\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "\n",
    "        # print(intervals, ans)\n",
    "        for idx in range(1, len(intervals)):\n",
    "            if intervals[idx][0] < intervals[idx-1][1]:\n",
    "                if intervals[idx][1] > intervals[idx-1][1]:\n",
    "                    intervals[idx] = intervals[idx-1]\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        print(intervals)\n",
    "        ans = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] < intervals[i - 1][1]:\n",
    "                ans += 1\n",
    "                if intervals[i][1] > intervals[i - 1][1]:\n",
    "                    intervals[i] = intervals[i - 1]\n",
    "            # print('update:', intervals)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        temp = np.array(intervals)\n",
    "        index = np.argsort(temp[:,1])\n",
    "        temp = temp[index,:]\n",
    "        count = 0\n",
    "        save_index = 0\n",
    "        for i in range(1,temp.shape[0]):\n",
    "            if  temp[i,0] <temp[save_index,1]:\n",
    "                count = count +1\n",
    "            else:\n",
    "                save_index = i\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        ans,tmp=0,[]\n",
    "\n",
    "        while intervals:\n",
    "            itv=intervals.pop()\n",
    "            lt,rt=itv[0],itv[1]   \n",
    "            while  intervals:  \n",
    "                itv2=intervals.pop()\n",
    "                if lt<=itv2[0]: ##区间套，保留内层\n",
    "                    lt,rt=itv2[0],itv2[1] \n",
    "                    ans+=1\n",
    "                elif lt<itv2[1]:\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    intervals.append(itv2) \n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(int(x[0]),int(x[1])))\n",
    "        i = len(intervals)-2\n",
    "        num = 0\n",
    "        while i>=0:\n",
    "            if intervals[i][1] > intervals[i+1][0]:\n",
    "                intervals.pop(i)\n",
    "                num += 1\n",
    "            i -= 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0],x[1]),reverse=False)\n",
    "        count=0\n",
    "        tmp=[0,0]\n",
    "        if len(intervals)==1:\n",
    "            return 0\n",
    "        while len(intervals)>1:\n",
    "            if intervals[-1][0]<intervals[-2][1]:\n",
    "                tmp=intervals[-1]\n",
    "                intervals.pop()\n",
    "                intervals[-1]=tmp\n",
    "                count+=1\n",
    "            else:\n",
    "                intervals.pop()\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x: x[0])\n",
    "        # print(intervals)\n",
    "        left, cnt = intervals[-1][0], 0\n",
    "\n",
    "        for i in range(len(intervals) - 2, -1, -1):\n",
    "            # print(left, intervals[i])\n",
    "            if intervals[i][1] > left: \n",
    "                intervals.pop(i)\n",
    "                cnt += 1\n",
    "            else: left = intervals[i][0]\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x: x[1])\n",
    "        num = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] < intervals[i-1][1]:\n",
    "                num += 1\n",
    "                intervals[i][0] = intervals[i-1][0]\n",
    "                intervals[i][1] = intervals[i-1][1]\n",
    "        \n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        cnt = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i-1][1] > intervals[i][0]:\n",
    "                intervals[i] = intervals[i-1]\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        end, count = float('-inf'), 0\n",
    "        for s, e in sorted(intervals, key=lambda x: x[1]):\n",
    "            if s >= end:\n",
    "                end = e\n",
    "            else: \n",
    "                intervals.pop()\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x: x[1], reverse=True)\n",
    "        n = len(intervals)\n",
    "        cnt = 0\n",
    "        while intervals:\n",
    "            p = intervals.pop()\n",
    "            cnt += 1\n",
    "            while intervals:\n",
    "                if intervals[-1][0]< p[1] and intervals[-1][1] >= p[1]:\n",
    "                    intervals.pop()\n",
    "                else:\n",
    "                    break\n",
    "        return n - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: x[1])\n",
    "        count = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] < intervals[i-1][1]:\n",
    "                count += 1\n",
    "                intervals[i] = intervals[i-1]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        remo = 0\n",
    "\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i - 1][1] > intervals[i][0]:\n",
    "                if intervals[i - 1][1] <= intervals[i][1]:\n",
    "                    intervals[i] = intervals[i - 1]\n",
    "                remo += 1\n",
    "        return remo                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0] < intervals[i-1][1]:\n",
    "                res = res+1\n",
    "                intervals[i] = intervals[i-1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        remove_num = 0\n",
    "        if len(intervals) <= 1:\n",
    "            return remove_num\n",
    "        intervals.sort(key = lambda x : x[1])\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] < intervals[i - 1][1]:\n",
    "                remove_num += 1\n",
    "                if intervals[i][1] >= intervals[i - 1][1]:\n",
    "                    intervals[i] = intervals[i-1]\n",
    "        return remove_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals)==0:return 0\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        result=0\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0]>=intervals[i-1][1]:\n",
    "                continue\n",
    "            else:\n",
    "                result+=1\n",
    "                intervals[i][0]=intervals[i-1][0]\n",
    "                intervals[i][1]=intervals[i-1][1]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i + 1 < len(intervals):\n",
    "            a, b = intervals[i], intervals[i + 1]\n",
    "            if b[0] < a[1]:\n",
    "                if b[1] < a[1]:\n",
    "                    intervals[i] = intervals[i + 1]\n",
    "                else:\n",
    "                    intervals[i + 1] = intervals[i]\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        #print(intervals)\n",
    "        res = 0\n",
    "        for i in range(1,len(intervals)):\n",
    "            #print(intervals[i][0],intervals[i-1][1])\n",
    "            if intervals[i][0] < intervals[i-1][1]:\n",
    "                res += 1\n",
    "                intervals[i][1] = min(intervals[i][1],intervals[i-1][1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n=len(intervals)\n",
    "        intervals.sort(key=lambda x: (x[0],-x[1]))\n",
    "        print(intervals)\n",
    "        i=len(intervals)-2\n",
    "        while i >=0:\n",
    "            if intervals[i][0] <= intervals[i + 1][0] and intervals[i][1] >= intervals[i + 1][1]:\n",
    "                intervals.pop(i)\n",
    "            i = i - 1\n",
    "\n",
    "        i=1\n",
    "        while i<len(intervals):\n",
    "            if intervals[i][0]<intervals[i-1][1] :\n",
    "                intervals.pop(i)\n",
    "                i=i-1\n",
    "            i=i+1\n",
    "        return n-len(intervals)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        dp = 0\n",
    "        n = len(intervals)\n",
    "        pre = intervals[0][0]\n",
    "        pop_list = []\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][0] == pre:\n",
    "                pop_list.append(i)\n",
    "                dp += 1\n",
    "            else:\n",
    "                pre = intervals[i][0]\n",
    "        for i in reversed(pop_list):\n",
    "            intervals.pop(i)\n",
    "        n = len(intervals)\n",
    "        most_left = intervals[-1][0]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if intervals[i][1] > most_left:\n",
    "                dp += 1\n",
    "            else:\n",
    "                most_left = intervals[i][0]\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0]>=intervals[i-1][1]:\n",
    "                continue\n",
    "            else:\n",
    "                count+=1\n",
    "                intervals[i][1]=min(intervals[i-1][1],intervals[i][1])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        stack = []\n",
    "        for s, e in intervals:\n",
    "            if stack and stack[-1][1] > e: \n",
    "                stack.pop(-1)\n",
    "                stack.append((s,e))\n",
    "                continue\n",
    "            if not stack or stack[-1][1] <= s: \n",
    "                stack.append((s, e))\n",
    "        return len(intervals) - len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda a: a[1])\n",
    "        right = intervals[0][1]\n",
    "        res = 1\n",
    "        for s, e in intervals:\n",
    "            if s >= right:\n",
    "                res += 1\n",
    "                right = e\n",
    "        \n",
    "        return len(intervals) - res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        \n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        f = [1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f.append(max((f[j] for j in range(i) if intervals[j][1] <= intervals[i][0]), default=0) + 1)\n",
    "\n",
    "        return n - max(f)\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        \n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        f = [0]*n\n",
    "        f[0]=1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if intervals[j][1] <= intervals[i][0]:\n",
    "                    f[i]=max(f[i],f[j]+1)\n",
    "\n",
    "        return n - max(f)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        if n == 0: return 0\n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "        intervals.sort(key=lambda a: a[0])\n",
    "\n",
    "        for i in range(len(intervals)):\n",
    "            for j in range(i - 1, -1, -1): ### 倒着排序\n",
    "                if intervals[i][0] >= intervals[j][1]:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "                    break # 由于是按照开始时间排序的, 因此可以剪枝\n",
    "                \n",
    "        return n - max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        b = sorted(set(end for start, end in intervals))\n",
    "        b = [-inf] + b\n",
    "        d = {v:i for i, v in enumerate(b)}\n",
    "        mx = [0] * b.__len__() * 4\n",
    "        L = 0\n",
    "        R = b.__len__() - 1\n",
    "\n",
    "        def query(idx, L, R, l, r)->int:\n",
    "            nonlocal mx\n",
    "            mid = (L + R) // 2\n",
    "            if L >= l and R <= r:\n",
    "                return mx[idx]\n",
    "            m = -inf \n",
    "            if l <= mid:\n",
    "                m = max(m, query(2*idx+1, L, mid, l, r))\n",
    "            if r > mid:\n",
    "                m = max(m, query(2*idx+2, mid+1, R, l, r))\n",
    "            return m\n",
    "        \n",
    "        def update(idx, L, R, n, val):\n",
    "            nonlocal mx\n",
    "            if L == R:\n",
    "                mx[idx] = max(mx[idx], val)\n",
    "                return \n",
    "            mid = (L + R) // 2\n",
    "            if n <= mid:\n",
    "                update(2*idx+1, L, mid, n, val)\n",
    "            else:\n",
    "                update(2*idx+2, mid+1, R, n, val)\n",
    "            mx[idx] = max(mx[2*idx+1], mx[2*idx+2])\n",
    "\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        for start, end in intervals:\n",
    "            m = query(0, 0, b.__len__()-1, 0, bisect_right(b, start)-1)\n",
    "            update(0, 0, b.__len__()-1, d[end], m+1)\n",
    "            \n",
    "        return intervals.__len__() - query(0, 0, b.__len__()-1, 0, b.__len__()-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        b = sorted(set(end for start, end in intervals))\n",
    "        b = [-inf] + b\n",
    "        d = {v:i for i, v in enumerate(b)}\n",
    "        mx = [0] * b.__len__() * 4\n",
    "        L = 0\n",
    "        R = b.__len__() - 1\n",
    "\n",
    "        def query(idx, L, R, l, r)->int:\n",
    "            nonlocal mx\n",
    "            mid = (L + R) // 2\n",
    "            if L >= l and R <= r:\n",
    "                return mx[idx]\n",
    "            m = -inf \n",
    "            if l <= mid:\n",
    "                m = max(m, query(2*idx+1, L, mid, l, r))\n",
    "            if r > mid:\n",
    "                m = max(m, query(2*idx+2, mid+1, R, l, r))\n",
    "            return m\n",
    "        \n",
    "        def update(idx, L, R, n, val):\n",
    "            nonlocal mx\n",
    "            if L == R:\n",
    "                mx[idx] = max(mx[idx], val)\n",
    "                return \n",
    "            mid = (L + R) // 2\n",
    "            if n <= mid:\n",
    "                update(2*idx+1, L, mid, n, val)\n",
    "            else:\n",
    "                update(2*idx+2, mid+1, R, n, val)\n",
    "            mx[idx] = max(mx[2*idx+1], mx[2*idx+2])\n",
    "\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        for start, end in intervals:\n",
    "            m = query(0, 0, b.__len__()-1, 0, bisect_right(b, start)-1)\n",
    "            update(0, 0, b.__len__()-1, d[end], m+1)\n",
    "            \n",
    "        return intervals.__len__() - query(0, 0, b.__len__()-1, 0, b.__len__()-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals=sorted(intervals)\n",
    "        \n",
    "        n=len(intervals)\n",
    "        start=intervals[0][0]\n",
    "        end=intervals[0][1]\n",
    "        cnt=0\n",
    "        print(intervals)\n",
    "        for i in range(1,n):\n",
    "            s,e=intervals[i]\n",
    "            if s<end:\n",
    "                cnt+=1\n",
    "                end=min(end,e)\n",
    "            else:\n",
    "                end=e\n",
    "\n",
    "            \n",
    "            \n",
    "                \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals = sorted(intervals, key=lambda x: x[1])\n",
    "\n",
    "        res = 0\n",
    "        pivot = 0\n",
    "        while pivot < len(intervals):\n",
    "            n = pivot + 1\n",
    "            while (n < len(intervals) and intervals[n][0] < intervals[pivot][1]):\n",
    "                res += 1\n",
    "                n += 1\n",
    "            pivot = n\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort()\n",
    "        ans = 0\n",
    "        for i in range(1,n):\n",
    "            if intervals[i][0] < intervals[i-1][1]:\n",
    "                ans += 1\n",
    "                intervals[i][1] = min(intervals[i][1], intervals[i-1][1])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return \n",
    "        \n",
    "        n = len(intervals)\n",
    "        intervals.sort(key = lambda x: x[1])\n",
    "        count = 1\n",
    "        right = intervals[0][1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][0] >= right:\n",
    "                count += 1\n",
    "                right = intervals[i][1]\n",
    "        \n",
    "        return n - count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
